package com.LeetCode.String;

import org.junit.Test;

import java.util.HashSet;
import java.util.List;

/**
 * 字节跳动 查找同分异构次
 * 例如 在 akcabbaabca   abac  -- > abca
 */
public class findStr {

    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
            73, 79, 83, 89, 97, 101};

    public String findStr(String s , String pattern){
        int patternHash = 1;
        char[] patterns = pattern.toCharArray();
        for(char c : patterns){
            patternHash *= primes[c - 'a'];
        }

        int len = s.length();
        int patternLen = pattern.length();

        int curHash = 1;

        char[] chars = s.toCharArray();


        for(int i = 0; i<patternLen; i++){
            curHash *= primes[s.charAt(i)-'a'];
        }

        int l = 0, r = patternLen;

        while(r < len){
            curHash /= primes[chars[l++]-'a'];
            curHash *= primes[chars[r++]-'a'];
            if(curHash == patternHash){
                return s.substring(l , r);
            }
        }
        return "";
    }

    HashSet<Integer> set = new HashSet<>();





    @Test
    public void test(){
        System.out.println(findStr("akcabbaabca","abac"));
    }

}
























